package queue;

public class CircleDeque<E> {
	
	private static final int DEFAULT_CAPACITY = 10;
	
	private E[] elements;
	private int size;
	private int front;
	
	public CircleDeque() {
		elements = (E[])new Object[DEFAULT_CAPACITY];
	}
	
	/**
	 * 元素的数量
	 * @return
	 */
	public int size() {
		return size;
	}
	
	/**
	 * 队列是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return size == 0;
	}
	
	/**
	 * 清空队列
	 */
	public void clear() {
		for (int i = 0; i < size; i++) {
			elements[index(i)] = null;
		}
		size = 0;
		front = 0;
	}
	
	/**
	 * 从队头入队
	 * @param element
	 */
	public void enQueueFront(E element) {
		ensureCapacity(size + 1);
		front = index(-1);
		elements[front] = element;
		size++;
	}
	/**
	 * 从队尾入队
	 * @param element
	 */
	public void enQueueRear(E element) {
		ensureCapacity(size + 1);
		int rear = index(size);
		elements[rear] = element;;
		size++;
	}
	
	/**
	 * 从队头出队
	 * @return
	 */
	public E deQueueFront() {
		checkEmpty();
		E element = elements[front];
		front = index(1);
		size--;
		return element;
	}
	
	/**
	 * 从队尾出队
	 * @return
	 */
	public E deQueueRear() {
		checkEmpty();
		E element = elements[index(size - 1)];
		size--;
		return element;
	}
	
	/**
	 * 获取队头元素
	 * @return
	 */
	public E front() {
		checkEmpty();
		return elements[front];
	}
	
	/**
	 * 获取队尾元素
	 * @return
	 */
	public E rear() {
		checkEmpty();
		return elements[index(size - 1)];
	}
	
	private int index(int index) {
		index += front;
		if (index < 0) return index + elements.length;
		return index - (index >= elements.length ? elements.length : 0);
	}
	
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		if (oldCapacity >= capacity) return;
		E[] newElements = (E[])new Object[oldCapacity + (oldCapacity >> 1)];
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[index(i)];
		}
		elements = newElements;
		front = 0;
	}
	
	private void checkEmpty() {
		if (size == 0) throw new IndexOutOfBoundsException("CircleDeque is empty");
	}
}
